package fun.ticsmyc.question;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 1590. 使数组和能被 P 整除
 * 面试题 17.05. 字母与数字
 */
public class 前缀和加哈希表 {

    public int minSubarray(int[] nums, int p) {
        Map<Integer, List<Integer>> book = new HashMap<>();
        int sum = 0;
        for (int num : nums) {
            sum = (sum + num) % p;
        }
        if (sum == 0) {
            return 0;
        }
        int need = sum % p;
        int res = Integer.MAX_VALUE;
        int cur = 0;
        for (int i = 0; i < nums.length; ++i) {
            cur = (cur + nums[i]) % p;
            //找前面余数是cur-need
            int find = (cur - need + p) % p;
            if (find == 0 && i + 1 != nums.length) {
                res = Math.min(res, i + 1);
            } else if (book.containsKey(find)) {
                List<Integer> list = book.get(find);
                res = Math.min(res, i - list.get(list.size() - 1));
            }
            List<Integer> list = book.computeIfAbsent(cur, key -> new ArrayList<>());
            list.add(i);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }


    public String[] findLongestSubarray(String[] array) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(-1);
        map.put(0, integers);
        int numCnt = 0, charCnt = 0;
        int resIndex = -1, resLen = 0;
        for (int i = 0; i < array.length; i++) {
            if (Character.isDigit(array[i].charAt(0))) {
                numCnt++;
            } else {
                charCnt++;
            }
            int cur = numCnt - charCnt;
            if (map.containsKey(cur)) {
                List<Integer> list = map.get(cur);
                if (i - list.get(0) > resLen) {
                    resLen = i - list.get(0);
                    resIndex = list.get(0) + 1;
                }
            }
            List<Integer> list = map.computeIfAbsent(cur, key -> new ArrayList<>());
            list.add(i);
        }
        if (resLen == 0) {
            return new String[]{};
        } else {
            String[] res = new String[resLen];
            System.arraycopy(array, resIndex, res, 0, resLen);
            return res;
        }
    }
}
